#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
    int numIslands(vector<vector<char>> &grid)
    {
        int ret = 0;
        function<void(int, int)> dfs = [&](int x, int y)
        {
            for (int i = 0; i < 4; ++i)
            {
                int hx = x + dx[i], hy = y + dy[i];
                if (hx >= 0 && hx < grid.size() && hy >= 0 && hy < grid[0].size())
                {
                    if (grid[hx][hy] == '1')
                    {
                        grid[hx][hy] = '0';
                        dfs(hx, hy);
                    }
                }
            }
        };
        for (int i = 0; i < grid.size(); ++i)
        {
            for (int j = 0; j < grid[i].size(); ++j)
            {
                if (grid[i][j] == '1')
                {
                    ++ret;
                    dfs(i, j);
                }
            }
        }
        return ret;
    }
};